import java.util.Arrays;
import java.util.Comparator;

/*
 * @lc app=leetcode.cn id=435 lang=java
 *
 * [435] 无重叠区间
 */

// @lc code=start
class Solution {
    // 又是贪心
    // 注意他没说要连续，只需要消除重叠即可
    /*
    按照起点排序：选择结尾最短的，后面才可能连接更多的区间（如果两个区间有重叠，应该保留结尾小的） 
    把问题转化为最多能保留多少个区间，使他们互不重复，则按照终点排序，每个区间的结尾很重要，结尾越小，则后面越有可能容纳更多的区间。
    */
    public int eraseOverlapIntervals(int[][] intervals) {
        int count = 1;//这是记录不重叠区间的个数
        int len = intervals.length;
        if(len == 0) return 0;
        //先按照区间尾的大小从小到大排序
        Arrays.sort(intervals, (a,b)->a[1]-b[1]);//这就是从小到大排序
        // Arrays.sort(intervals, new Comparator<int[] >(){
        //     @Override
        //     public int compare(int[] a, int[] b) {
        //         return a[1]-b[1];
        //     }
        // });//用Comparator的方式用的存储空间会貌似少一点
    
        int end = intervals[0][1];//这是第一个节点的尾部
        for(int i=1;i<len;i++){
            if(intervals[i][0]>=end){//如果begin>=end,说明没有重叠，可以加入
                end=intervals[i][1];//更新end
                count++;
            }
        }

        return len-count;//这是没用上的，就是重叠的。
    }
}
// @lc code=end

